//
// Created by liushuai on 2021/1/16.
//

#include "reConstructBinaryTree.h"

TreeNode* reConstructBinaryTree(std::vector<int> pre, std::vector<int> vin) {
  if (pre.size() <= 0)
    return nullptr;
  else {
    int root_value = pre[0];
    TreeNode* root = new TreeNode(root_value);
    int root_index = std::distance(
        vin.begin(), std::find(vin.begin(), vin.end(), root_value));
    std::vector<int> left_pre = std::vector<int>(root_index, 0);
    std::vector<int> left_in = std::vector<int>(root_index, 0);
    std::vector<int> right_pre =
        std::vector<int>(pre.size() - root_index - 1, 0);
    std::vector<int> right_in =
        std::vector<int>(pre.size() - root_index - 1, 0);

    std::copy(pre.begin() + 1, pre.begin() + root_index + 1, left_pre.begin());
    std::copy(pre.begin() + root_index + 1, pre.end(), right_pre.begin());
    std::copy(vin.begin(), vin.begin() + root_index, left_in.begin());
    std::copy(vin.begin() + root_index + 1, vin.end(), right_in.begin());
    root->left = reConstructBinaryTree(left_pre, left_in);
    root->right = reConstructBinaryTree(right_pre, right_in);
    return root;
  }
}